package Graph.graphWithWeight.MinistedTree.Prim;

import Graph.graphWithWeight.EdgeWeight;
import Graph.graphWithWeight.GraphWeight;
import Graph.graphWithWeight.MinistedTree.Kruskal.ConnectComponent;

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Author: 蔡翔
 * @Date: 2020/3/1 9:25
 * @Version 1.0
 * prim 算法 引入 优先队列 优化；核心就是先把 0节点的周围边放入优先对线，只要从堆顶一直取堆顶元素，然后对堆顶元素周围的边也放入优先队列 就行了。
 */
public class PrimPlus {
    private GraphWeight G;
    private ArrayList<EdgeWeight> mst;

    public PrimPlus(GraphWeight G){
        this.G = G;
        mst = new ArrayList<>();
        ConnectComponent cc = new ConnectComponent(G);
        if(cc.count()>1){return;}
        //prim
        //切分开始 分成 1 和 v-1 部分，用bool表示切分
        boolean[] visited = new boolean[G.V()];
        visited[0] = true;

        //因为EdgeWeight 已近实现了Comparable<EdgeWeight>接口，所以PriorityQueue拿出来的边就是权值最小值的表
        Queue pq = new PriorityQueue<EdgeWeight>();
        //因为0 周围所有的边 都是 横切边，所以初始化只要 把0顶点周围的边都加入就行了
        for(int w:G.adj(0)){
            pq.add(new EdgeWeight(0,w,G.getWeight(0,w)));
        }
        while (!pq.isEmpty()){
            EdgeWeight minEdge = (EdgeWeight)pq.remove();
            //如果这条边的两个顶点都为true说明在一个 横切区域内。 这也是判别是否合法横切边 的原因。
            if(visited[minEdge.getV()] && visited[minEdge.getW()]){
                continue;
            }
            mst.add(minEdge);
            //判别出 哪个才是 新增的 横切边
            int newv = visited[minEdge.getV()]?minEdge.getW():minEdge.getV();
            visited[newv] = true;
            for(int w:G.adj(newv)){
                if(!visited[w]){
                    pq.add(new EdgeWeight(newv,w,G.getWeight(newv,w)));
                }
            }
        }

    }

    public ArrayList<EdgeWeight> result(){
        return mst;
    }

    public static void main(String[] args) {
        GraphWeight g = new GraphWeight("gPrim.txt");
        PrimPlus prim = new PrimPlus(g);
        System.out.println(prim.result());
    }
}
